// 给定一个链表的头节点head，判断链表是否有环

// 1. 哈希表
// 遍历所有节点，每次都用哈希表判断该节点是否被访问过，如果访问过就说明存在环，如果没有则
// 添加到哈希表中，继续遍历判断
const { ListNode, LinkedList } = require('../../1. 链表基础/1. 建立线性链表')

// 时间复杂度：O(n)
// 空间复杂度：O(n)
function hasCycle(head) {
    let set = new Set()

    while (head) {
        if (set.has(head)) {
            return true
        } else {
            set.add(head)
            head = head.next
        }
    }
    return false
}

let list = new LinkedList([2, 5, 1, 7, 3, 9, 1])
let node1 = new ListNode(2)
let node2 = new ListNode(5)
let node3 = new ListNode(1)
let node4 = new ListNode(7)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1

console.log(hasCycle(list.head));
console.log(hasCycle(node1));

// 2. 快慢指针（Floyd判圈算法）
// 类似于操场跑步，两个人从同一位置出发，如果跑到有环，那么快的一方总能追上慢的一方
// Floyd使用两个指针，慢指针每次前进一步，快指针每次前进两步，如果两个指针在链表头节点以外的某个节点相遇了，那说明链表有环


// 时间复杂度：O(n)
// 空间复杂度：O(1)
function hasCycle2(head) {
    if (!head || !head.next) {
        return false
    }
    let slow = head
    let fast = head.next
    while (slow !== fast) {
        if (!fast || !fast.next) {
            return false
        }
        slow = slow.next
        fast = fast.next.next
    }
    return true
}
// console.log(hasCycle2(list.head));
// console.log(hasCycle2(node1));
